package test230610;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/10 0:39
 * 128. 最长连续序列
 * https://leetcode.cn/problems/longest-consecutive-sequence/
 */
public class Solution02 {

    // 哈希思想 时间复杂度 O(n)
    public int longestConsecutive2(int[] nums) {
        // 先使用 HashSet 进行去重, 同时起到了优化查找的功能
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int ans = 0;
        // 遍历去重后的所有数字
        for (int num : set) {
            // 只有当 num - 1 不存在的时候, 依次遍历 num + 1、 num + 2...
            // 即找到连续序列的起点
            if (!set.contains(num - 1)) {
                int cur = num;
                while (set.contains(cur)) {
                    ++cur;
                }
                // 由于连续序列是公差为 1 的等差数列, 因此, curLen = cur - 1 - num + 1 = cur - num
                ans = Math.max(ans, cur - num);
            }
        }
        return ans;
    }

    // 动态规划 + 排序思考, 时间复杂度 O(nlog(n))
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        Arrays.sort(nums);
        int[] dp = new int[n];  // dp[i] 表示以 i 结尾的序列中的连续序列的长度
        int maxLen = 1;  // 记录结果
        dp[0] = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i - 1] + 1 == nums[i]) {
                // 连续
                dp[i] = dp[i - 1] + 1;
            } else if (nums[i - 1] == nums[i]){
                dp[i] = dp[i - 1];
            } else {
                dp[i] = 1;
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}
